import string
import copy
from Queue import Queue
from Queue import PriorityQueue

mymax = 1e16
mymin = 1e-8


class Item:
    def __init__(self):
        self.fnum = 0
        self.cnum = 0
        self.f = []
        self.u = []
        self.c = []
        self.p = []

class QFacItem:
    def __init__(self, fid, updateid):
        self.fid = fid
        self.updateid = updateid

class FacItem:
    def __init__(self, vol, updatetime, updateid, contributors):
        self.vol = 1.0 * vol
        self.updatetime = 1.0 * updatetime
        self.updateid = updateid
        self.contributors = contributors
        
    def updatedata(self, current_time, conchange):
        self.vol -= self.contributors * (current_time - self.updatetime)
        self.updatetime = current_time
        self.contributors += conchange
        self.updateid +=1
    
def InitQFacItem(data):
    mylist = PriorityQueue()
    for i in range(0, data.fnum):
        mylist.put((mymax, QFacItem(i, 0)))
    return mylist

def InitFacItem(data):
    mylist = []
    for i in range(0, data.fnum):
        mylist.append(FacItem(data.f[i], 0.0, 0, 0))
    return mylist

def GetExpectFillTime(fit):
    if fit.contributors <= 0:
        return mymax
    return fit.updatetime + fit.vol / fit.contributors

def ReadFile(filename):
    fl = open(filename)
    numset = []
    while True:
        line = fl.readline()
        if not line:
            break
        line = line.replace('\n','')
        if not line:
            continue
        while line[-1] == ' ':
            line = line[0:-1]
        arr = line.split(' ')
        for st in arr:
            numset.append(string.atof(st))
            
    lmt = len(numset)
    if lmt < 2:
        exit()

    data = Item()
    
    data.fnum = int(numset[0])
    data.cnum = int(numset[1])
    
    iternum = 2

    while True:
        if (len(data.f) >= data.fnum):
            break
        if (iternum >= lmt):
            exit()
        data.f.append(numset[iternum])
        iternum = iternum + 1


    while True:
        if (len(data.u) >= data.fnum):
            break
        if (iternum >= lmt):
            exit()
        data.u.append(numset[iternum])
        iternum = iternum + 1


    while True:
        if (len(data.p) >= data.cnum):
            break
        if (iternum >= lmt):
            exit()
        data.p.append(numset[iternum])
        iternum = iternum + 1


    c_i = []
    while True:
        if (len(data.c) >= data.fnum):
            break
        if (iternum >= lmt):
            exit()
        c_i.append(numset[iternum])
        iternum = iternum + 1
        if (len(c_i) >= data.cnum):
            data.c.append(c_i)
            c_i = []
    fl.close()
    return data

def ChangeProblem(data, lbd):
    data_= copy.deepcopy(data)
    for i in range(0, data.fnum):
        data_.f[i] = data.f[i] * lbd
    for i in range(0, data.fnum):
        for j in range(0, data.cnum):
            data_.c[i][j] = data_.c[i][j] + data.f[i] * 1.0 / data.u[i]
    for i in range(0, data.fnum):
        data_.u[i] = data.cnum + 1
    return data_


def GetEdgeList(data):
    pq = PriorityQueue()
    for i in range(0, data.fnum):
        for j in range(0, data.cnum):
            pq.put((data.c[i][j], i, j))
    for j in range(0, data.cnum):
        pq.put((data.p[j], -1, j))
    return pq

def GetSetFopen(data, fac, alpha):
    ans = []
    occu = []
    for i in range(0, data.fnum):
        occu.append(False)
    j_occu = []
    for j in range(0, data.cnum):
        j_occu.append(False)
    while True:
        mintime = mymax
        mini = -1
        for i in range(0, data.fnum):
            if occu[i]== False and fac[i].vol <= mymin:   #Opened and not occupied fac
                if mintime > fac[i].updatetime:
                    mintime = fac[i].updatetime
                    mini = i
        if mini == -1:
            break
        ans.append(mini)
        occu[mini] = True
        for j in range(0, data.cnum):
            if j_occu[j] == False and data.c[mini][j] <= alpha[j]:
                j_occu[j] = True
                for i in range(0, data.fnum):
                    if occu[i] == False and data.c[i][j] <= alpha[j]:
                        occu[i] = True
    return ans

def Gain(data, client, addi):
    ans = -data.f[addi]
    for j in range(0, data.cnum):
        if data.c[addi][j] < data.c[client[j]][j]:
            ans += data.c[client[j]][j] - data.c[addi][j]
    return ans


def AnsUpdate(data, F, client):
    for j in range(0, data.cnum):
        minc = mymax
        for i in F:
            if data.c[i][j] < minc:
                minc = data.c[i][j]
                client[j] = i

def AnsUpdateOne(data, addi, client):
    for j in range(0, data.cnum):
        if data.c[addi][j] < data.c[client[j]][j]:
            client[j] = addi
            
        
        

    

    




